package com.example.leetcode.c601_c700.c697;
/**
 * 给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。
 *
 * 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：[1, 2, 2, 3, 1]
 * 输出：2
 * 解释：
 * 输入数组的度是2，因为元素1和2的出现频数最大，均为2.
 * 连续子数组里面拥有相同度的有如下所示:
 * [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
 * 最短连续子数组[2, 2]的长度为2，所以返回2.
 * 示例 2：
 *
 * 输入：[1,2,2,3,1,4,2]
 * 输出：6
 *  
 *
 * 提示：
 *
 * nums.length 在1到 50,000 区间范围内。
 * nums[i] 是一个在 0 到 49,999 范围内的整数。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/degree-of-an-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import java.util.*;

/**
 * 数组的度
 * @author zhanpengguo
 * @date 2021-02-20 8:33
 */
public class Solution {

    public int findShortestSubArray(int[] nums) {
        // map的value数组包含三个元素，第一个表示元素出现的次数，第二个和第三个分表表示元素出现的第一个位置和最后一个位置
        Map<Integer, int[]> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            if (map.containsKey(num)) {
                map.get(num)[0]++;
                map.get(num)[2] = i;
            } else {
                map.put(num, new int[]{1, i, i});
            }
        }
        int mostNum = -1, minLen = 0;
        for (Map.Entry<Integer, int[]> entry : map.entrySet()) {
            int[] value = entry.getValue();
            if (value[0] > mostNum) {
                mostNum = value[0];
                minLen = value[2] - value[1] + 1;
            } else if (value[0] == mostNum) {
                int len = value[2] - value[1] + 1;
                if (minLen > len) {
                    minLen = len;
                }
            }
        }
        return minLen;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1,2,2,3,1,4,2};
        int i = solution.findShortestSubArray(nums);
        System.out.println(i);
    }
}
